package com.study.leetcode;

//https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
/*
       dp 动态规划
       have[i] 表示第 i 天持有股票，那么就只能是今天买入或者之前就有
       no[i] 表示第 i 天没有持有股票，那么就只能是今天卖出或者之前就没有
       当前题为无限次购买，不过存在冷冻期而已
       状态转移方程：
       1、普通的无限次股票购买：
           have[i] = Math.max(have[i - 1], no[i - 1] - prices[i]);
           no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
       2、含冷冻期的无限次股票购买
           have[i] = Math.max(have[i - 1], no[i - 2] - prices[i]);
           no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
       差别在于 have[i] 方程中的 no[i - 1] 和 no[i - 2]
       no[i - 1] 表示昨天没有持有股票，昨天没有持有的话有两种可能：
           1、之前都没有持有，那么 no[i - 1] = no[i - 2]
           2、昨天卖出股票，那么今天就是冷冻期了，那么今天不能购买
       因此如果今天要购买的话，那么只能是选择昨天没有卖出股票的情况，即 no[i - 2]
       初始条件：
       have[0] = -prices[0], no[0] = 0
       have[0] 表示如果第一天持有的话只能买入，收益为 -prices[0]
       no[0] 表示第一天不持有，那么无作为，收益为 0
*/
public class Solution_309 {
    public int maxProfit(int[] prices) {

        int len = prices.length;
        if (len == 0) {
            return 0;
        }
        int[] have = new int[len];
        int[] no = new int[len];
        have[0] = -prices[0];
        no[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i - 1], i >= 2 ? no[i - 2] - prices[i] : -prices[i]);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return no[len - 1];
    }
}
